package week02

// 面试题 04.06. 后继者
// https://leetcode-cn.com/problems/successor-lcci/

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	return inorderSuccessor2(root, p, nil)
}

func inorderSuccessor2(root, p, m *TreeNode) *TreeNode {
	if root == nil {
		return m
	}
	if root.Val > p.Val {
		// 往左边找
		if m == nil || m.Val > root.Val {
			m = root
		}
		return inorderSuccessor2(root.Left, p, m)
	} else if root.Val < p.Val {
		// 往右边找
		return inorderSuccessor2(root.Right, p, m)
	} else {
		// 找到了
		if root.Right == nil {
			return m
		}
		// 有右子树，找最左边的点
		r := root.Right
		for r.Left != nil {
			r = r.Left
		}
		return r
	}
}
type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}
